//: C17:Sieve.cpp
// From Thinking in C++, 2nd Edition
// Available at http://www.BruceEckel.com
// (c) Bruce Eckel 1999
// Copyright notice in Copyright.txt
#include <string>
#include <iostream>
using namespace std;

int main()
{
    // Create a 50 char string and set each
    // element to 'P' for Prime
    string sieveChars(50, 'P');
    // By definition neither 0 nor 1 is prime.
    // Change these elements to "N" for Not Prime
    sieveChars.replace(0, 2, "NN");
    // Walk through the array:
    for (int i = 2;
            i <= (sieveChars.size() / 2) - 1; i++)
        // Find all the factors:
        for (int factor = 2;
                factor * i < sieveChars.size(); factor++)
            sieveChars[factor * i] = 'N';

    cout << "Prime:" << endl;
    // Return the index of the first 'P' element:
    int j = sieveChars.find('P');
    // While not at the end of the string:
    while (j != sieveChars.npos) {
        // If the element is P, the index is a prime
        cout << j << " ";
        // Move past the last prime
        j++;
        // Find the next prime
        j = sieveChars.find('P', j);
    }
    cout << "\n Not prime:" << endl;
    // Find the first element value not equal P:
    j = sieveChars.find_first_not_of('P');
    while (j != sieveChars.npos) {
        cout << j << " ";
        j++;
        j = sieveChars.find_first_not_of('P', j);
    }
} ///:~
